package com.algorithm.dynamic;

import java.util.Map;

public class Dynamic {
    public static void main(String[] args) {
        KnapscakProblem();
    }

    public static void KnapscakProblem(){
        int[] w = {1,4,3};              //物品重量
        int[] val = {1500,3000,2000};   //物品价值
        int m = 4;                      //背包重量
        int n = val.length;             //物品个数
        //v[i][j]为装入前i个物品，背包容量为j时背包的最大价值
        //第一行和第一列为0，数组默认为0，所以可以不用处理
        int[][] v = new int[n+1][m+1];
        //用于存放背包中放入的商品
        int[][] path = new int[n+1][m+1];
        //按照公式获取最优解
        for(int i = 1; i<v.length;i++){
            for(int j = 1;j<v[i].length;j++){
                if(w[i-1] > j ){
                    v[i][j] = v[i-1][j];
                }else {
                    v[i][j] = Math.max(v[i-1][j],v[i-1][j-w[i-1]]+val[i-1]);
                    path[i][j] = v[i-1][j] < v[i-1][j-w[i-1]]+val[i-1] ? 1:0;
                }
            }
        }

        for (int v1[]:v){
            for (int v2 : v1){
                System.out.print(v2+" ");
            }
            System.out.println();
        }
        System.out.println("---------------------");

        //从后往前输出装入背包的路径
        int i = path.length - 1;
        int j = path[0].length - 1;
        while(i > 0 && j > 0 ){
            if(path[i][j] == 1){
                System.out.println("第"+i+"个商品放入背包");
                //输出第i个商品以后，背包重量减去该商品的重量
                j -= w[i-1];
            }
            i--;
        }
    }
}
